package stack;

import stack.MyStack;

import java.util.*;

public class Test {

    public static void main(String[] args) {
        //ArrayList 和 LinkedList都是实体类
        //List、Queue 和 Deque 都是接口

        //栈是实现类，先进后出
        //底层可以通过数组和链式模拟实现(满足特性即可)。底层本就是数组(动态扩容数组)
        Stack<Integer> stack1 = new Stack<>();
        List<Integer> stack2 = new Stack<>();

        //队列是接口，先进先出
        //底层可以通过链表和数组模拟实现(满足特性即可)。底层本就是链表
        //普通队列
        Queue<Integer> queue1 = new LinkedList<>();
        Queue<Integer> queue2 = new ArrayDeque<>();

        //双端队列，底层是双向链表实现的。
        Deque<Integer> deque1 = new LinkedList<>();//双端队列链式实现
        Deque<Integer> deque2 = new ArrayDeque<>();//双端队列线性实现

        //双端队列不仅可以当做队列使用，也可以当做栈使用
        Deque<Integer> queue = new LinkedList<>();//双端队列链式实现
        Deque<Integer> stack = new ArrayDeque<>();//双端队列线性实现

        //双端队列线性实现 -》 当做栈使用
        //双端队列链式实现 -》 当做队列使用

        //队列
        Queue<Integer> queue11 = new LinkedList<>();
        //链表
        List<Integer> queue22 = new LinkedList<>();
    }









    //出栈入栈次序匹配
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        //遍历第一个序列并压栈
        for (int i = 0; i < popV.length; i++) {
            stack.push(pushV[i]);
            //判断栈顶元素是否与第二序列j位置的元素是否相同
            while (!stack.empty() && j < popV.length && stack.peek() == popV[j]) {
                stack.pop();
                j++;
            }
        }
        //栈中是否还有元素
        return stack.empty();
        /*if (!stack.empty()) {
            return false;
        }
        return true;*/
    }





    //括号匹配
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        //1.遍历字符串
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            //2.判断是否是左括号
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                //3.遇到了右括号
                //判断是否是第一次遇见右括号 同时判断了字符串没有遍历完，栈就为空的情况
                if (stack.empty()) {
                    return false;
                }
                char ch2 = stack.peek();//ch2是左括号，获取栈顶元素不删除 此时ch是右括号
                //出栈的左括号是否跟此时右括号匹配
                if ((ch2 == '(' && ch == ')') || (ch2 == '{' && ch == '}') || (ch2 == '[' && ch == ']')) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if(!stack.empty()) {
            return false;
        }
        return true;
    }



    //逆波兰表达式计算
    public int evalRPN(String[] tokens) {
        //创建一个栈
        Stack<Integer> stack = new Stack<>();
        //遍历后缀表达式
        for (String x : tokens) {
            //如果是操作数，放到栈中
            if (!isOperation(x)) {
                //这里将String类类型拆行为int基本类型并压栈
                //压栈时自动装箱
                stack.push(Integer.parseInt(x));
            } else {
                //如果是运算符则需要弹出栈顶两个元素，作为操作数进行运算
                //第一个为右边操作数，第二个左边操作数
                int num2 = stack.pop();
                int num1 = stack.pop();
                /*if (x.equals("+")) {
                    stack.push(num1 + num2);
                }
                if (x.equals("-")) {
                    stack.push(num1 - num2);
                }
                if (x.equals("*")) {
                    stack.push(num1 * num2);
                }
                if (x.equals("/")) {
                    stack.push(num1 / num2);
                }*/
                //这里用switch语句更简洁，如果用if语句形式太多太复杂
                //判断是哪种运算符，并进行运行
                switch (x) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                }
            }
        }
        //走完for循环，栈内就剩一个元素了 即计算后的结果，直接返回
        return stack.pop();
    }

    //判断是否是运算符
    private boolean isOperation(String s) {
        //return (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
            return true;
        } else {
            return false;
        }
    }



    public static void main3(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push(10);
        myStack.push(20);
        myStack.push(30);
        myStack.push(40);
        myStack.push(50);
        myStack.display();
        System.out.println(myStack.size());
        System.out.println(myStack.empty());//是否为空
        System.out.println(myStack.full());//是否满了
        System.out.println("====================");
        myStack.pop();//50 出栈
        System.out.println(myStack.pop()); //40 出栈
        myStack.peek();//30
        System.out.println(myStack.peek());


    }


    public static void main2(String[] args) {
        Stack<Integer> stack = new Stack<>();
        System.out.println(stack.empty());
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);

        System.out.println(stack);
        System.out.println(stack.pop());
        System.out.println(stack);
        stack.peek();
        stack.peek();
        System.out.println(stack);
        System.out.println(stack.size());
        System.out.println(stack.empty());
    }

    public static void main1(String[] args) {
        Stack<Integer> s = new Stack();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.size()); // 获取栈中有效元素个数---> 4
        System.out.println(s.peek()); // 获取栈顶元素---> 4
        s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
        System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为2
        if (s.empty()) {
            System.out.println("栈空");
        } else {
            System.out.println(s.size());
        }
    }

}
